#include <cstdlib>
#include <iostream>
#include <ctime>
#include "grafo.h"
#include "busqueda_tabu.h"

using namespace std;

class Grafo leerInput(istream&);
void escribirOutput(ostream&, const vector<uint>&);
timespec diff(timespec start, timespec end);

Grafo leerInput(istream& is) {
	uint n, m;
	is >> n >> m;

	Grafo grafo(n);
	for (int k=0; k < m; k++) {
		uint i, j;
		is >> i >> j;
		grafo.agregarArista(i,j);
	}
	
	return grafo;
}

ostream& operator<<(ostream &os, vector<uint> &solucion) {
	for(vector<uint>::iterator it = solucion.begin(); it != solucion.end(); it++)
		os << (*it) << " ";
	os << endl;
	return os;
}


int main() {
	
	#ifdef TESTING
		timespec start, end, result;
		clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	#endif
	
	Grafo grafo = leerInput(cin);

	CliqueMaximaFronteraTabu iniciar(grafo);

	vector<uint> solucion = iniciar.resolver();

	#ifdef TESTING
		clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
		result = diff(start, end);
		cout << result.tv_sec * (unsigned long) 1000000000 + result.tv_nsec << endl;
	#endif

	#ifndef TESTING
		cout << solucion;
	#endif

	return 0;
}

timespec diff(timespec start, timespec end) {
	timespec temp;
	if((end.tv_nsec - start.tv_nsec) < 0) {
		temp.tv_sec = end.tv_sec - start.tv_sec - 1;
		temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
	} else	{
		temp.tv_sec = end.tv_sec - start.tv_sec;
		temp.tv_nsec = end.tv_nsec - start.tv_nsec;
	}
	return temp;
}
